#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

struct ListNode {
    int data;
    ListNode *next;
    ListNode(int x) : data(x), next(NULL) {}
};

vector<ListNode *> myVec;

void printlist(ListNode *list)
{
    ListNode *cur = list;
    
     do {
        cout << list->data << " ";
        list = list->next;
    } while (list != cur);
    cout << endl;
}

void insertList (ListNode *&node, int num)
{
    if (!node) {
	node = new ListNode(num);
        node->next = node;
	return;
    }

    ListNode *newNode = new ListNode(num);
    myVec.push_back(newNode);
    ListNode *tmp = node;
    ListNode *cur = tmp;
    do {
        if (cur->next && cur->data <= num && num <= cur->next->data) {
            newNode->next = cur->next;
            cur->next = newNode;
	    return;
	}	 
        if (cur->next && ((cur->data > cur->next->data && num <= cur->next->data) ||
            (cur->data > cur->next->data && num >= cur->data))) {
            newNode->next = cur->next;
            cur->next = newNode;
	    return;
	}
	cur = cur->next;
    } while(cur != tmp);
    cout << "Insert here" << endl; 
    newNode->next = cur->next;
    cur->next = newNode;
    return;
}

int main(int argc, char **argv)
{
    ListNode *head = NULL;
    int A[] = {1,4,5,7,8,9,12,12,12,13,14,15,15,15,16,17,19,20};
    insertList(head, A[0]);
    myVec.push_back(head); 
    for (int i = 1; i < sizeof(A)/sizeof(int); i++) {
       ListNode *cur = myVec[rand()%myVec.size()];
       ListNode *tmp = cur;
       cout << "Before" << endl;
       printlist(cur);
       insertList(cur, A[i]);
       cout << "After" << endl;
       printlist(cur);
       cout << endl;
    } 

    return 0;
}
